package com.atguigu.search;

import java.util.Arrays;

/**
 * @author shkstart
 * @create 2021-08-16 11:33
 */
//插值查找算法适用于数据量比较大，关键字分布比较均匀的查找表，速度较快
//插值查找算法查找次数只需要一次就够,因为mid算法的改变，称之为自适应

public class InsertValueSearch {
    public static void main(String[] args) {
        int arr[] = {3, 22, -6, 89, 89, 89, 54, 677, 0};

        Arrays.sort(arr);
//        //测试
//        int[] arr = new int[100];
//        for (int i=0;i<100;i++){
//            arr[i]=i+1;
//        }
//        System.out.println(Arrays.toString(arr));
        int index = insertValueSearch(arr, 0, arr.length-1, 677);
        System.out.println("index="+index);
    }
    //插值查找算法
    public static int insertValueSearch(int []arr,int left,int right,int findValue){
        //判断失败的条件
        if (left>right||findValue<arr[0]||findValue>arr[arr.length-1]){
            return -1;
        }
        int mid=left+(right-left)*(findValue-arr[left])/(arr[right]-arr[left]);
        int midVal=arr[mid];
        if (findValue>midVal){
            return insertValueSearch(arr,mid+1,right,findValue);
        }else if (findValue<mid){
            return insertValueSearch(arr,left,mid-1,findValue);
        }else{
            return mid;
        }

    }
}
